package leetcode.图.拓扑排序;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/5 10:36
 * @description :
 */
public class 课程表 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.canFinish(2, new int[][]{{1, 0}, {0, 1}}));

    }



    // BFS
    /*
    class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            // 获取入度数组
            int[] inDeg = new int[prerequisites.length];
            for (int i = 0; i < prerequisites.length; i++) {
                inDeg[prerequisites[i][0]]++;
            }
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < inDeg.length; i++) {
                if (inDeg[i] == 0) {
                    queue.offer(i);
                }
            }
            int count = 0;
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                count++;
                for (int[] prerequisite : prerequisites) {
                    // 所有以cur为出度的节点，入段减一
                    if (prerequisite[1] == cur && --inDeg[prerequisite[0]] == 0) {
                        queue.offer(prerequisite[0]);
                    }
                }
            }
            return count == numCourses;
        }
    }
     */

    class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            List<List<Integer>> edges = new ArrayList<>();
            int[] inDeg = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                edges.add(new ArrayList<>());
            }
            for (int[] prerequisite : prerequisites) {
                edges.get(prerequisite[1]).add(prerequisite[0]);
                inDeg[prerequisite[0]]++;
            }
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < inDeg.length; i++) {
                if (inDeg[i] == 0) {
                    queue.offer(i);
                }
            }
            int count = 0;
            while (!queue.isEmpty()) {
                Integer cur = queue.poll();
                count++;
                for (Integer in : edges.get(cur)) {
                    if (--inDeg[in] == 0) {
                        queue.offer(in);
                    }
                }
            }
            return count == numCourses;
        }
    }

}
